package main

import (
	"crypto/md5"
	"fmt"
	"math"
	"math/rand"
	"sort"
	"strconv"
	"strings"
	"unicode"
)

type Solution struct {
	dict map[int][]int
}

func Constructor(nums []int) Solution {
	s := Solution{
		dict: make(map[int][]int, 0),
	}
	for i := 0; i < len(nums); i++ {
		ins, ok := s.dict[nums[i]]
		if ok {
			ins = append(ins, i)
		} else {
			ins = make([]int, 0)
			ins = append(ins, i)
		}
		s.dict[nums[i]] = ins
	}
	return s
}

func (this *Solution) Pick(target int) int {
	ints := this.dict[target]
	return ints[rand.Intn(len(ints))]
}

func binaryGap(n int) int {
	ans := 0
	index := 0
	for (n >> index) > 0 {
		num := (n >> index) & 1
		if num == 1 {
			for i := index + 1; (n >> i) > 0; i++ {
				if (n>>i)&1 == 1 {
					ans = int(math.Max(float64(ans), float64(i-index)))
					break
				}
			}
		}
		index++
	}
	return ans
}

func projectionArea(grid [][]int) int {
	xy := 0
	yz := 0
	xz := 0
	for i := 0; i < len(grid); i++ {
		max := 0
		for j := 0; j < len(grid[i]); j++ {
			max = int(math.Max(float64(max), float64(grid[i][j])))
			if grid[i][j] != 0 {
				xy++
			}
		}
		xz += max
	}
	for i := 0; i < len(grid[0]); i++ {
		max := 0
		for j := 0; j < len(grid); j++ {
			max = int(math.Max(float64(max), float64(grid[j][i])))
		}
		yz += max
	}
	return xy + yz + xz
}

func pacificAtlantic(heights [][]int) [][]int {
	ans := make([][]int, 0)
	m := len(heights)
	n := len(heights[0])
	pacific := make([][]bool, m)
	atlantic := make([][]bool, m)
	for i := 0; i < m; i++ {
		pacific[i] = make([]bool, n)
		atlantic[i] = make([]bool, n)
	}
	var dfs func(i, j, pre int, visited [][]bool)
	dfs = func(i, j, pre int, visited [][]bool) {
		if i < 0 || j < 0 || i == m || j == n || visited[i][j] || heights[i][j] > pre {
			return
		}
		visited[i][j] = true
		dfs(i, j, heights[i-1][j], visited)
		dfs(i, j, heights[i+1][j], visited)
		dfs(i, j, heights[i][j-1], visited)
		dfs(i, j, heights[i][j+1], visited)
	}
	for i := 0; i < m; i++ {
		dfs(i, 0, heights[i][0], pacific)
		dfs(i, n-1, heights[i][n-1], atlantic)
	}
	for i := 0; i < n; i++ {
		dfs(0, i, heights[0][i], pacific)
		dfs(m-1, i, heights[m-1][i], atlantic)
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if pacific[i][j] && atlantic[i][j] {
				ans = append(ans, []int{i, j})
			}
		}
	}
	return ans
}

func sortArrayByParity(nums []int) []int {
	ans := make([]int, len(nums))
	left := 0
	right := len(nums) - 1
	for i := 0; left <= right; i++ {
		if nums[i]%2 == 0 {
			ans[left] = nums[i]
			left++
		} else {
			ans[right] = nums[i]
			right--
		}
	}
	return ans
}

type Node struct {
	Val         bool
	IsLeaf      bool
	TopLeft     *Node
	TopRight    *Node
	BottomLeft  *Node
	BottomRight *Node
}

func construct(grid [][]int) *Node {
	var dfs func(r0, c0, r1, c1 int) *Node
	dfs = func(r0, c0, r1, c1 int) *Node {
		same := true
		for i := r0; i < r1 && same; i++ {
			for j := c0; j < c1; j++ {
				if grid[r0][c0] != grid[i][j] {
					same = false
					break
				}
			}
		}
		if same {
			return &Node{Val: grid[r0][c0] == 1, IsLeaf: true}
		}
		return &Node{
			Val:         true,
			IsLeaf:      false,
			TopLeft:     dfs(r0, c0, (r0+r1)/2, (c0+c1)/2),
			TopRight:    dfs(r0, (c0+c1)/2, (r0+r1)/2, c1),
			BottomLeft:  dfs((r0+r1)/2, c0, r1, (c0+c1)/2),
			BottomRight: dfs((r0+r1)/2, (c0+c1)/2, r1, c1),
		}
	}
	return dfs(0, 0, len(grid), len(grid))
}

func smallestRangeI(nums []int, k int) int {
	min := 10000
	max := 0
	for i := 0; i < len(nums); i++ {
		min = int(math.Min(float64(min), float64(nums[i])))
		max = int(math.Max(float64(max), float64(nums[i])))
	}
	if max-min <= 2*k {
		return 0
	} else {
		return max - min - 2*k
	}
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func getAllElements(root1 *TreeNode, root2 *TreeNode) []int {
	one := make([]int, 0)
	two := make([]int, 0)
	var dfs func(root *TreeNode, list *[]int)
	dfs = func(root *TreeNode, list *[]int) {
		if root == nil {
			return
		}
		dfs(root.Left, list)
		*list = append(*list, root.Val)
		dfs(root.Right, list)
	}
	dfs(root1, &one)
	dfs(root2, &two)
	i1 := 0
	i2 := 0
	i3 := 0
	ans := make([]int, len(one)+len(two))
	for i1 < len(one) && i2 < len(two) {
		if one[i1] < two[i2] {
			ans[i3] = one[i1]
			i1++
		} else {
			ans[i3] = two[i2]
			i2++
		}
		i3++
	}
	for i := i1; i < len(one); i++ {
		ans[i3] = one[i]
		i3++
	}
	for i := i2; i < len(two); i++ {
		ans[i3] = two[i]
		i3++
	}
	return ans
}

func reorderLogFiles(logs []string) []string {
	// true 小的再前，false 大的在前
	sort.SliceStable(logs, func(i, j int) bool {
		s, t := logs[i], logs[j]
		s1 := strings.SplitN(s, " ", 2)[1]
		s2 := strings.SplitN(t, " ", 2)[1]
		isDigit1 := unicode.IsDigit(rune(s1[0]))
		isDigit2 := unicode.IsDigit(rune(s2[0]))
		if isDigit1 && isDigit2 {
			return false
		}
		if !isDigit1 && !isDigit2 {
			return s1 < s2 || s1 == s2 && s < t
		}
		return !isDigit1
	})
	return logs
}

func findTheWinner(n int, k int) int {
	ans := make([]int, n)
	for i := 1; i <= n; i++ {
		ans[i-1] = i
	}
	index := 1
	for len(ans) > 1 {
		pop := ans[0]
		if index%k != 0 {
			ans = append(ans, pop)
		}
		ans = ans[1:]
		index++
	}
	return ans[0]
}

func numSubarrayProductLessThanK(nums []int, k int) int {
	pre := 1
	ans := 0
	left := 0
	right := 0
	for right > len(nums) {
		pre = pre * nums[right]
		right++
		for left < right && pre >= k {
			pre /= nums[left]
			left++
		}
		ans += right - left
	}
	return ans
}

type RecentCounter struct {
	list []int
}

//func Constructor() RecentCounter {
//	return RecentCounter{
//		list: make([]int, 0),
//	}
//}

func (this *RecentCounter) Ping(t int) int {
	this.list = append(this.list, t)
	for len(this.list) > 0 && this.list[len(this.list)-1]-this.list[0] > 3000 {
		this.list = this.list[1:]
	}
	return len(this.list)
}

func minMutation(start string, end string, bank []string) int {
	// 定义合法的基因仓库
	banks := make(map[string]int)
	// 存储已经变过的基因序列，防止重复判断
	isvisited := make(map[string]int)
	// 可变的单个基因序列
	chars := []byte{'A', 'T', 'G', 'C'}
	// 定义变化的过程队列
	queue := make([]string, 0)
	// 存储合法的基因序列，方便判断
	for i := range bank {
		banks[bank[i]] += 1
	}
	// 已经相同 不用改变
	if start == end {
		return 0
	}
	// 结果不在合法的基因序列中，改变不成功
	if _, ok := banks[end]; !ok {
		return -1
	}
	// 记录初始访问的基因序列
	isvisited[start] += 1
	queue = append(queue, start)
	// 默认会改变一次
	step := 1
	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			poll := queue[i]
			bytes := []byte(poll)
			// 挨个基因序列尝试
			for j := 0; j < 8; j++ {
				temp := bytes[j]
				for k := 0; k < 4; k++ {
					// 如果不相同，尝试改变
					if chars[k] != temp {
						bytes[j] = chars[k]
						s := string(bytes)
						bytes[j] = temp
						_, ok := banks[s]
						_, visited := isvisited[s]
						// 如果合法
						if ok && !visited {
							// 相等直接返回改变次数
							if s == end {
								return step
							}
							// 否则加入队列，等待下次的尝试
							queue = append(queue, s)
							isvisited[s] += 1
						}
					}
				}
			}
		}
		// 去除已经尝试过的基因序列和次数+1
		queue = queue[size:]
		step++
	}
	return -1
}

func findDuplicates(nums []int) []int {
	dict := make(map[int]int)
	ans := make([]int, 0)
	for i := 0; i < len(nums); i++ {
		i2 := nums[i]
		dict[i2] += 1
		if dict[i2] == 2 {
			ans = append(ans, i2)
		}
	}
	return ans
}

func diStringMatch(s string) []int {
	left := 0
	right := len(s)
	ans := make([]int, len(s)+1)
	for i := 0; i < len(s); i++ {
		if s[i] == 'I' {
			ans[i] = left
			left++
		} else {
			ans[i] = right
			right--
		}
	}
	ans[len(s)] = right
	return ans
}

func averageOfSubtree(root *TreeNode) int {
	ans := 0
	var dfs func(root *TreeNode) []int
	dfs = func(root *TreeNode) []int {
		if root == nil {
			return []int{0, 0}
		}
		left := dfs(root.Left)
		right := dfs(root.Right)
		all := []int{root.Val, 1}
		all[0] += left[0] + right[0]
		all[1] += left[1] + right[1]
		if all[0]/all[1] == root.Val {
			ans++
		}
		return all
	}
	constructor := Constructor2()
	fmt.Println(constructor)
	dfs(root)
	return ans
}

type Codec struct {
}

func Constructor2() Codec {
	return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
	if root == nil {
		return "null"
	}
	ins := make([]*TreeNode, 0)
	s := ""
	ins = append(ins, root)
	for len(ins) > 0 {
		size := len(ins)
		for i := 0; i < size; i++ {
			if ins[i] != nil {
				s += strconv.Itoa(ins[i].Val) + ","
				ins = append(ins, ins[i].Left)
				ins = append(ins, ins[i].Right)
			} else {
				s += "null,"
			}
		}
		ins = ins[size:]
	}
	return s[:len(s)-1]
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
	if len(data) == 0 {
		return nil
	}
	split := strings.Split(data, ",")
	nodes := make([]*TreeNode, len(split)+1)
	for i := 1; i < len(nodes); i++ {
		if split[i-1] != "null" {
			atom, _ := strconv.Atoi(split[i-1])
			nodes[i] = &TreeNode{
				Val: atom,
			}
		}
	}
	index := 0
	for i := 1; i < len(nodes); i++ {
		if nodes[i] == nil {
			continue
		}
		index++
		if index*2 < len(nodes) {
			nodes[i].Left = nodes[index*2]
		}
		if index*2+1 < len(nodes) {
			nodes[i].Right = nodes[index*2+1]
		}
	}
	return nodes[1]
}

func minDeletionSize(strs []string) int {
	l := len(strs[0])
	ans := 0
	for i := 0; i < l; i++ {
		var min byte = 'A'
		for j := 0; j < len(strs); j++ {
			if strs[j][i] >= min {
				min = strs[j][i]
			} else {
				ans++
				break
			}
		}
	}
	return ans
}

func oneEditAway(first string, second string) bool {
	if int(math.Abs(float64(len(first)-len(second)))) > 1 {
		return false
	}
	if len(first) < len(second) {
		first, second = second, first
	}
	i, j, diff := 0, 0, 0
	for i < len(first) && j < len(second) && diff <= 1 {
		if first[i] == second[j] {
			i++
			j++
		} else {
			if len(first) == len(second) {
				i++
				j++
				diff++
			} else {
				i++
				diff++
			}
		}
	}
	return diff <= 1
}

func isAlienSorted(words []string, order string) bool {
	hash := make(map[byte]int)
	for i := range order {
		hash[order[i]] = i
	}
	var check func(s1, s2 string) bool
	check = func(s1, s2 string) bool {
		l1 := len(s1)
		l2 := len(s2)
		m, n := 0, 0
		for m < l1 && n < l2 {
			if hash[s1[m]] > hash[s2[n]] {
				return false
			} else if hash[s1[m]] < hash[s2[n]] {
				return true
			}
			m++
			n++
		}
		return l1 <= l2
	}
	for i := 1; i < len(words); i++ {
		if !check(words[i-1], words[i]) {
			return false
		}
	}
	return true
}

func inorderSuccessor(root *TreeNode, p *TreeNode) *TreeNode {
	var dfs func(root, p *TreeNode) *TreeNode
	dfs = func(root, p *TreeNode) *TreeNode {
		if root == nil {
			return nil
		}
		if p.Val >= root.Val {
			return dfs(root.Right, p)
		}
		node := dfs(root.Left, p)
		if node != nil {
			return node
		}
		return root
	}
	return dfs(root, p)
}

func repeatedNTimes(nums []int) int {
	dict := make(map[int]int, 0)
	ans := 0
	for i := 0; i < len(nums); i++ {
		dict[nums[i]] += 1
		if dict[nums[i]] == len(nums)/2 {
			ans = nums[i]
			break
		}
	}
	return ans
}

func isUnivalTree(root *TreeNode) bool {
	val := root.Val
	var dfs func(root *TreeNode) bool
	dfs = func(root *TreeNode) bool {
		if root == nil {
			return true
		}
		if root.Val != val {
			return false
		}
		return dfs(root.Left) && dfs(root.Right)
	}
	return dfs(root)
}

func findClosest(words []string, word1 string, word2 string) int {
	ans, left, right := math.MaxInt64, -1, -1
	for i := range words {
		if word1 == words[i] {
			left = i
		}
		if word2 == words[i] {
			right = i
		}
		if left != -1 && right != -1 {
			ans = int(math.Min(float64(ans), math.Abs(float64(right-left))))
		}
	}
	return ans
}

func removeOuterParentheses(s string) string {
	ans := ""
	left := 0
	right := 0
	start := 0
	for i := range s {
		if s[i] == '(' {
			left++
		} else {
			right++
		}
		if left == right {
			ans += s[start+1 : i]
			left = 0
			right = 0
			start = i + 1
		}
	}
	return ans
}

func sumRootToLeaf(root *TreeNode) int {
	ans := 0
	var sumRootToLeafDfs func(root *TreeNode, s string)
	sumRootToLeafDfs = func(root *TreeNode, s string) {
		if root == nil {
			return
		}
		if root.Left == nil && root.Right == nil {
			for i := range s {
				if s[i] != '0' {
					ans += int(math.Pow(float64(2), float64(len(s)-1-i)))
				}
			}

			return
		}
		s += strconv.Itoa(root.Val)
		sumRootToLeafDfs(root.Left, s)
		sumRootToLeafDfs(root.Right, s)
	}
	return ans
}

func generate(numRows int) [][]int {
	ints := make([]int, numRows)
	ints[0] = 1
	ans := make([][]int, 5)
	for i := 0; i < numRows; i++ {
		for j := 0; j >= 0; j-- {
			if j > 0 {
				ints[j] += ints[j-1]
			}
		}
		fmt.Println(ints)
		in := make([]int, 0)
		for k := 0; k <= i; k++ {
			in = append(in, ints[k])
		}
		ans[i] = in
	}
	return ans
}

func deleteNode(root *TreeNode, key int) *TreeNode {
	if root == nil {
		return root
	}
	if root.Val == key {
		if root.Left == nil {
			return root.Right
		}
		if root.Right == nil {
			return root.Left
		}
		min := findMin(root.Right)
		root.Val = min.Val
		root.Right = deleteNode(root.Right, min.Val)
	} else if root.Val > key {
		root.Left = deleteNode(root.Left, key)
	} else {
		root.Right = deleteNode(root.Right, key)
	}
	return root
}

func findMin(root *TreeNode) *TreeNode {
	if root.Left == nil {
		return root
	}
	return findMin(root.Left)
}

func numUniqueEmails(emails []string) int {
	set := make(map[string]int)
	for i := range emails {
		split := strings.Split(emails[i], "@")
		split[0] = strings.ReplaceAll(split[0], ".", "")
		index := strings.Index(split[0], "+")
		if index != -1 {
			split[0] = split[0][0:index]
		}
		_, ok := set[split[0]+"@"+split[1]]
		if !ok {
			set[split[0]+"@"+split[1]] += 1
		}
	}
	return len(set)
}

func isBoomerang(points [][]int) bool {
	return (points[0][0]-points[1][0])*(points[0][1]-points[2][1]) != (points[0][0]-points[2][0])*(points[0][1]-points[1][1])
}

func findAndReplacePattern(words []string, pattern string) []string {
	ans := make([]string, 0)
	for i := range words {
		flag := true
		one := make(map[byte]byte)
		two := make(map[byte]byte)
		for j := 0; j < len(words[i]) && flag; j++ {
			if _, ok := one[words[i][j]]; !ok {
				one[words[i][j]] = pattern[j]
			}
			if _, ok := two[pattern[j]]; !ok {
				two[pattern[j]] = one[words[i][j]]
			}
			if one[words[i][j]] != pattern[j] || two[pattern[j]] != words[i][j] {
				flag = false
			}
		}
		if flag {
			ans = append(ans, words[i])
		}
	}
	return ans
}

func heightChecker(heights []int) int {
	ans := 0
	newHeight := make([]int, len(heights))
	for i := range heights {
		newHeight[i] = heights[i]
	}
	sort.Slice(newHeight, func(i, j int) bool {
		return newHeight[i] < newHeight[j]
	})
	for i := range heights {
		if newHeight[i] != heights[i] {
			ans++
		}
	}
	return ans
}

func findPairs(nums []int, k int) int {
	if k < 0 {
		return 0
	}
	visited := make(map[int]int)
	diff := make(map[int]int)
	for i := range nums {
		if _, ok := visited[nums[i]+k]; ok {
			diff[nums[i]] += 1
		}
		if _, ok := visited[nums[i]-k]; ok {
			diff[nums[i]-k] += 1
		}
		visited[nums[i]] = 1
	}
	return len(diff)
}

func duplicateZeros(arr []int) {
	newArr := make([]int, len(arr))
	for i := range arr {
		newArr[i] = arr[i]
	}
	index := 0
	for i := 0; i < len(arr) && index < len(arr); i++ {
		if newArr[i] != 0 {
			arr[index] = newArr[i]
			index++
		} else {
			arr[index] = newArr[i]
			if index < len(arr) {
				arr[index+1] = newArr[i]
			}
			index += 2
		}
	}
}

func findBottomLeftValue(root *TreeNode) int {
	queue := make([]*TreeNode, 0)
	ans := 0
	for len(queue) > 0 {
		ans = queue[0].Val
		size := len(queue)
		for i := 0; i < size; i++ {
			node := queue[i]
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		queue = queue[size:]
	}
	return ans
}

func largestValues(root *TreeNode) []int {
	queue := make([]*TreeNode, 0)
	ans := make([]int, 0)
	if root != nil {
		queue = append(queue, root)
	}
	for len(queue) > 0 {
		size := len(queue)
		max := math.MinInt
		for i := 0; i < size; i++ {
			node := queue[i]
			max = int(math.Max(float64(node.Val), float64(max)))
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		ans = append(ans, max)
		queue = queue[size:]
	}
	return ans
}

func wiggleSort(nums []int) {
	length := len(nums)
	ints := make([]int, length)
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})
	index := length - 1
	for i := 1; i >= 0; i-- {
		for j := i; j < length; j += 2 {
			ints[j] = nums[index]
			index--
		}
	}
	for i := 0; i < length; i++ {
		nums[i] = ints[i]
	}
}

type Codec2 struct {
	urlMap map[string]string
}

func Constructor1() Codec2 {
	return Codec2{
		urlMap: map[string]string{},
	}
}

// Encodes a URL to a shortened URL.
func (this *Codec2) encode(longUrl string) string {
	Md5Inst := md5.New()
	Md5Inst.Write([]byte(longUrl))
	Result := Md5Inst.Sum([]byte(""))
	newUrl := "http://tinyurl.com/" + string(Result)
	this.urlMap[newUrl] = longUrl
	return newUrl
}

// Decodes a shortened URL to its original URL.
func (this *Codec2) decode(shortUrl string) string {
	return this.urlMap[shortUrl]
}

func minimumAbsDifference(arr []int) [][]int {
	sort.Slice(arr, func(i, j int) bool {
		return arr[i] < arr[j]
	})
	dict := make(map[int][][]int)
	min := int(math.MinInt)
	for i := 0; i <= len(arr)-2; i++ {
		abs := int(math.Abs(float64(arr[i]) - float64(arr[i+1])))
		min = int(math.Min(float64(min), float64(abs)))
		if list, ok := dict[abs]; ok {
			list = append(list, []int{arr[i], arr[i+1]})
			dict[abs] = list
		} else {
			list = append(list, []int{arr[i], arr[i+1]})
			dict[abs] = list
		}
	}
	return dict[min]
}

type MyCalendar struct {
	list [][]int
}

func Constructor3() MyCalendar {
	return MyCalendar{list: make([][]int, 0)}
}

func (this *MyCalendar) Book(start int, end int) bool {
	for i := range this.list {
		l, r := this.list[i][0], this.list[i][1]
		if l < end && start < r {
			return false
		}
	}
	this.list = append(this.list, []int{start, end})
	return true
}

func minCostToMoveChips(position []int) int {
	even := 0
	odd := 0
	for i := range position {
		if position[i]%2 == 0 {
			even++
		} else {
			odd++
		}
	}
	return int(math.Min(float64(even), float64(odd)))
}

type MagicDictionary struct {
	dictionary []string
}

func Constructor7() MagicDictionary {
	return MagicDictionary{}
}

func (this *MagicDictionary) BuildDict(dictionary []string) {
	this.dictionary = dictionary
}

func (this *MagicDictionary) Search(searchWord string) bool {
	i := len(this.dictionary)
	for j := 0; j < i; j++ {
		s := this.dictionary[i]
		length := len(s)
		if length == len(searchWord) {
			diff := 0
			for k := 0; k < length; k++ {
				if searchWord[k] != s[k] {
					diff++
				}
			}
			if diff == 1 {
				return true
			}
		}
	}
	return false
}

func oddCells(m int, n int, indices [][]int) int {
	ints := make([][]int, m)
	for i := range ints {
		ints[i] = make([]int, n)
	}
	ans := 0
	for i := range indices {
		point := indices[i]
		for j := 0; j < len(ints[point[0]]); j++ {
			ints[point[0]][j]++
		}
		for k := 0; k < len(ints); k++ {
			ints[k][point[1]]++
		}
	}
	for i := range ints {
		for j := range ints[i] {
			if ints[i][j]%2 != 0 {
				ans++
			}
		}
	}
	return ans
}

func asteroidCollision(asteroids []int) []int {
	ans := make([]int, 0)
	for i := range asteroids {
		alive := true
		asteroid := asteroids[i]
		for alive && len(ans) > 0 && asteroid < 0 && ans[len(ans)-1] > 0 {
			alive = asteroid+ans[len(ans)-1] < 0
			if ans[len(ans)-1]+asteroid <= 0 {
				ans = ans[:len(ans)-1]
			}
		}
		if alive {
			ans = append(ans, asteroid)
		}
	}
	return ans
}

type MovingAverage struct {
	size int
	nums []int
	all  float64
}

/** Initialize your data structure here. */
func Constructor8(size int) MovingAverage {
	return MovingAverage{
		nums: make([]int, 0),
		size: size,
		all:  0,
	}
}

func (this *MovingAverage) Next(val int) float64 {
	this.nums = append(this.nums, val)
	this.all += float64(val)
	if len(this.nums) <= this.size {
		return this.all / float64(len(this.nums))
	} else {
		this.all -= float64(this.nums[len(this.nums)-this.size-1])
		return this.all / float64(this.size)
	}
}

func arrayNesting(nums []int) int {
	max := 0
	for i := range nums {
		if nums[i] == -1 {
			continue
		}
		currentNum := nums[i]
		currentMax := 1
		for i != currentNum {
			currentMax++
			num := nums[currentNum]
			nums[currentNum] = -1
			currentNum = num
		}
		max = int(math.Max(float64(currentMax), float64(max)))
	}
	return max
}

func shiftGrid(grid [][]int, k int) [][]int {
	m := len(grid)
	n := len(grid[0])
	ans := make([][]int, m)
	start := k % (m * n)
	ints := make([]int, m*n)
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			if start == m*n {
				start = 0
			}
			ints[start] = grid[i][j]
			start++
		}
	}
	index := 0
	for i := 0; i < m; i++ {
		in := make([]int, n)
		for j := 0; j < n; j++ {
			in[j] = ints[index]
			index++
		}
		ans = append(ans, in)
	}
	return ans
}

func pruneTree(root *TreeNode) *TreeNode {
	if root == nil {
		return nil
	}
	root.Left = pruneTree(root.Left)
	root.Right = pruneTree(root.Right)
	if root.Val == 0 && root.Right == nil && root.Left == nil {
		return nil
	}
	return root
}

type CBTInserter struct {
	list []*TreeNode
	root *TreeNode
}

func Constructor9(root *TreeNode) CBTInserter {
	domain := CBTInserter{
		list: make([]*TreeNode, 0),
		root: root,
	}
	q := make([]*TreeNode, 0)
	domain.list = append(domain.list, root)
	q = append(q, root)
	for len(q) > 0 {
		i := len(q)
		for j := 0; j < i; j++ {
			node := q[i]
			if node.Left != nil {
				domain.list = append(domain.list, node.Left)
			}
			if node.Right != nil {
				domain.list = append(domain.list, node.Right)
			}
			if domain.list[0].Left != nil && domain.list[0].Right != nil {
				domain.list = domain.list[1:]
			}
		}
		q = q[i:]
	}
	return domain
}

func (this *CBTInserter) Insert(val int) int {
	peek := this.list[0]
	if len(this.list) > 0 {
		treeNode := &TreeNode{
			Val: val,
		}
		if peek.Left == nil {
			peek.Left = treeNode
		} else if peek.Right == nil {
			peek.Right = treeNode
			this.list = this.list[1:]
		}
		this.list = append(this.list, treeNode)
	}
	return peek.Val
}

func (this *CBTInserter) Get_root() *TreeNode {
	return this.root
}

func arrayRankTransform(arr []int) []int {
	ints := make([]int, len(arr))
	copy(arr, ints)
	sort.Slice(ints, func(i, j int) bool {
		return i < j
	})
	m := make(map[int]int)
	index := 1
	for i := range ints {
		if _, ok := m[ints[i]]; !ok {
			m[ints[i]] = index
			index++
		}
	}
	for i := range arr {
		ints[i] = m[arr[i]]
	}
	return ints
}

func maxLevelSum(root *TreeNode) int {
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	max := root.Val
	step := 1
	ans := 1
	for len(queue) > 0 {
		size := len(queue)
		all := 0
		for i := 0; i < size; i++ {
			node := queue[i]
			all += node.Val
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		if all > max {
			max = all
			ans = step
		}
		step++
		queue = queue[size:]
	}
	return ans
}

func generateTheString(n int) string {
	if n%2 == 0 {
		return strings.Repeat("a", n-1) + "b"
	} else {
		return strings.Repeat("a", n)
	}
}

type N struct {
	val    int
	after  *N
	before *N
}

type MyCircularQueue struct {
	size    int
	used    int
	root    *N
	current *N
}

func Constructor10(k int) MyCircularQueue {
	return MyCircularQueue{
		size: k,
		used: 0,
		root: nil,
	}
}

func (this *MyCircularQueue) EnQueue(value int) bool {
	if this.IsFull() {
		return false
	}
	n := &N{val: value}
	if this.root == nil {
		n.after = n
		n.before = n
		this.root = n
		this.current = n
	} else {
		this.current.before = n
		n.before = this.current
		n.after = this.root
		this.current = n
	}
	this.used++
	return true
}

func (this *MyCircularQueue) DeQueue() bool {
	if this.IsEmpty() {
		return false
	}
	if this.root == this.current {
		this.root = nil
		this.current = nil
	} else {
		root := this.root
		this.root = root.before
		this.root.after = root.after
	}
	this.used--
	return true
}

func (this *MyCircularQueue) Front() int {
	if this.IsEmpty() {
		return -1
	}
	return this.root.val
}

func (this *MyCircularQueue) Rear() int {
	if this.IsEmpty() {
		return -1
	}
	return this.current.val
}

func (this *MyCircularQueue) IsEmpty() bool {
	return this.used == 0
}

func (this *MyCircularQueue) IsFull() bool {
	return this.used == this.size
}

func orderlyQueue(s string, k int) string {
	if k == 1 {
		min := s
		newS := s
		for {
			f := newS[0]
			newS = newS[1:]
			newS = newS + string(f)
			if newS < min {
				min = newS
			}
			if newS == s {
				break
			}
		}
		return newS
	} else {
		bytes := []byte(s)
		sort.Slice(bytes, func(i, j int) bool {
			return bytes[i] < bytes[j]
		})
		return string(bytes)
	}
}

func minSubsequence(nums []int) []int {
	sort.IntSlice.Sort(nums)
	n := len(nums)
	all := 0
	curr := 0
	ans := make([]int, 0)
	for i := 0; i < n; i++ {
		all += nums[i]
	}
	for i := n - 1; i >= 0; i-- {
		ans = append(ans, nums[i])
		curr += nums[i]
		all -= nums[i]
		if curr > all {
			break
		}
	}
	return ans
}

func addOneRow(root *TreeNode, val int, depth int) *TreeNode {
	if depth == 1 {
		treeNode := &TreeNode{
			Val:  val,
			Left: root,
		}
		return treeNode
	} else {
		queue := make([]*TreeNode, 0)
		queue = append(queue, root)
		step := 1
		for len(queue) > 0 && step < depth {
			size := len(queue)
			for i := 0; i < size; i++ {
				node := queue[i]
				if depth-1 == step {
					left := node.Left
					right := node.Right
					node.Left = &TreeNode{
						Val:  val,
						Left: left,
					}
					node.Right = &TreeNode{
						Val:   val,
						Right: right,
					}
				} else {
					if node.Left != nil {
						queue = append(queue, node.Left)
					}
					if node.Right != nil {
						queue = append(queue, node.Right)
					}
				}
			}
			step++
			queue = queue[size:]
		}
		return root
	}
}

func stringMatching(words []string) []string {
	sort.Slice(words, func(i, j int) bool {
		return len(words[i]) < len(words[j])
	})
	ans := make([]string, 0)
	set := make(map[string]int)
	for i := 0; i < len(words); i++ {
		for j := i + 1; j < len(words); j++ {
			for k := 0; k <= len(words[j])-len(words[i]); k++ {
				subString := words[j][k : len(words[i])+k]
				if subString == words[i] {
					if _, ok := set[words[i]]; !ok {
						ans = append(ans, words[i])
						set[words[i]] += 1
					}
					break
				}
			}
		}
	}
	return ans
}

func exclusiveTime(n int, logs []string) []int {
	ans := make([]int, n)
	stack := make([][]int, 0)
	for i := range logs {
		split := strings.Split(logs[i], ":")
		n, _ := strconv.Atoi(split[0])
		t, _ := strconv.Atoi(split[2])
		if split[1] == "start" {
			stack = append(stack, []int{n, t})
		} else {
			pop := stack[len(stack)-1]
			ans[pop[0]] += t - pop[1] + 1
			stack = stack[0 : len(stack)-1]
			if len(stack) > 0 {
				ans[stack[len(stack)-1][0]] -= t - pop[1] + 1
			}
		}
	}
	return ans
}

func minStartValue(nums []int) int {
	ans := 1
	all := ans
	index := 0
	for index < len(nums) {
		all += nums[index]
		if all < 1 {
			ans++
			index = 0
			all = ans
		}
		index++
	}
	return ans
}

func reformat(s string) string {
	chars := []byte(s)
	c := make([]byte, 0)
	n := make([]byte, 0)
	for i := 0; i < len(chars); i++ {
		if chars[i] > '9' || chars[i] < '0' {
			c = append(c, chars[i])
		} else {
			n = append(n, chars[i])
		}

	}
	if math.Abs(float64(len(n))-float64(len(c))) > 1 {
		return ""
	}
	ci := 0
	ni := 0
	for i := 0; i < len(chars); i++ {
		if i%2 == 0 {
			if len(n) >= len(c) {
				chars[i] = n[ni]
				ni++
			} else {
				chars[i] = c[ci]
				ci++
			}
		} else {
			if len(c) >= len(n) {
				chars[i] = c[ci]
				ci++
			} else {
				chars[i] = n[ni]
				ni++
			}
		}
	}
	return string(chars)
}

func groupThePeople(groupSizes []int) [][]int {
	ans := make([][]int, 0)
	hashMap := make(map[int][]int)
	for i := 0; i < len(groupSizes); i++ {
		list := hashMap[groupSizes[i]]
		list = append(list, i)
		hashMap[groupSizes[i]] = list
	}
	for k, v := range hashMap {
		index := 0
		for i := 0; i < len(v)/k && index < len(v); i++ {
			list := make([]int, 0)
			for j := 0; j < k; j++ {
				list = append(list, v[index])
				index++
			}
			ans = append(ans, list)
		}
	}
	return ans
}

type MyCircularDeque struct {
	queue  []int
	length int
}

func Constructor11(k int) MyCircularDeque {
	return MyCircularDeque{
		queue:  make([]int, 0),
		length: k,
	}
}

func (this *MyCircularDeque) InsertFront(value int) bool {
	if this.IsFull() {
		return false
	}
	this.queue = append([]int{value}, this.queue...)
	return true
}

func (this *MyCircularDeque) InsertLast(value int) bool {
	if this.IsFull() {
		return false
	}
	this.queue = append(this.queue, value)
	return true
}

func (this *MyCircularDeque) DeleteFront() bool {
	if this.IsEmpty() {
		return false
	}
	this.queue = this.queue[1:]
	return true
}

func (this *MyCircularDeque) DeleteLast() bool {
	if this.IsEmpty() {
		return false
	}
	this.queue = this.queue[:len(this.queue)-1]
	return true
}

func (this *MyCircularDeque) GetFront() int {
	if this.IsEmpty() {
		return -1
	}
	return this.queue[0]
}

func (this *MyCircularDeque) GetRear() int {
	if this.IsEmpty() {
		return -1
	}
	return this.queue[len(this.queue)-1]
}

func (this *MyCircularDeque) IsEmpty() bool {
	return len(this.queue) == 0
}

func (this *MyCircularDeque) IsFull() bool {
	return len(this.queue) == this.length
}

type OrderedStream struct {
	m     map[int]string
	size  int
	index int
}

func Constructor12(n int) OrderedStream {
	return OrderedStream{
		m:     make(map[int]string),
		size:  n,
		index: 1,
	}
}

func (this *OrderedStream) Insert(idKey int, value string) []string {
	this.m[idKey] = value
	ans := make([]string, 0)
	for this.index <= this.size {
		if _, ok := this.m[this.index]; !ok {
			break
		}
		ans = append(ans, this.m[this.index])
		this.index++
	}
	return ans
}

func deepestLeavesSum(root *TreeNode) int {
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	ans := 0
	for len(queue) > 0 {
		i := len(queue)
		sum := 0
		for j := 0; j < i; j++ {
			poll := queue[j]
			sum += poll.Val
			if poll.Left != nil {
				queue = append(queue, poll.Left)
			}
			if poll.Right != nil {
				queue = append(queue, poll.Right)
			}
		}
		queue = queue[i:]
		if len(queue) == 0 {
			ans = sum
		}
	}
	return ans
}

func busyStudent(startTime []int, endTime []int, queryTime int) int {
	ans := 0
	for i := 0; i < len(startTime); i++ {
		if startTime[i] <= queryTime && endTime[i] >= queryTime {
			ans++
		}
	}
	return ans
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func constructMaximumBinaryTree(nums []int) *TreeNode {
	var dfs func(left, right int, nums []int) *TreeNode
	dfs = func(left, right int, nums []int) *TreeNode {
		if left > right {
			return nil
		}
		max := left
		for i := left; i <= right; i++ {
			if nums[i] > nums[max] {
				max = i
			}
		}
		node := &TreeNode{Val: nums[max]}
		node.Left = dfs(left, max-1, nums)
		node.Right = dfs(max+1, right, nums)
		return node
	}
	return dfs(0, len(nums)-1, nums)
}

func isPrefixOfWord(sentence string, searchWord string) int {
	split := strings.Split(sentence, " ")
	for i := range split {
		if strings.HasPrefix(split[i], searchWord) {
			return i + 1
		}
	}
	return -1
}

func canBeEqual(target []int, arr []int) bool {
	m := make(map[int]int)
	for i := range target {
		m[target[i]] = m[target[i]] + 1
	}
	for i := range arr {
		if j, ok := m[arr[i]]; !ok || j <= 0 {
			return false
		}
		m[arr[i]] -= 1
	}
	return true
}

func findClosestElements(arr []int, k int, x int) []int {
	sort.Slice(arr, func(i, j int) bool {
		if math.Abs(float64(arr[i]-x)) != math.Abs(float64(arr[j]-x)) {
			return math.Abs(float64(arr[i]-x)) < math.Abs(float64(arr[j]-x))
		} else {
			return arr[i] < arr[j]
		}
	})
	arr = arr[:k]
	sort.IntSlice.Sort(arr)
	return arr
}

func shuffle(nums []int, n int) []int {
	ans := make([]int, len(nums))
	l := 0
	r := n
	for i := 0; i < len(nums); i++ {
		ans[i] = nums[l]
		ans[i+1] = nums[r]
		l++
		r++
	}
	return ans
}

func maxProduct(nums []int) int {
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})
	return (nums[len(nums)-1] - 1) * (nums[len(nums)-2] - 1)
}

func finalPrices(prices []int) []int {
	for i := 0; i < len(prices); i++ {
		for j := i + 1; j < len(prices); j++ {
			if prices[i] >= prices[j] {
				prices[i] = prices[i] - prices[j]
				break
			}
		}
	}
	return prices
}

func numSpecial(mat [][]int) int {
	m := len(mat)
	n := len(mat[0])
	rows := make([]int, m)
	cols := make([]int, n)
	for i := 0; i < len(mat); i++ {
		for j := 0; j < len(mat[i]); j++ {
			if mat[i][j] == 1 {
				rows[i] += 1
				cols[j] += 1
			}
		}
	}
	ans := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if mat[i][j] == 1 && rows[i] == 1 && cols[j] == 1 {
				ans++
			}
		}
	}
	return ans
}

func maximumSwap(num int) int {
	max := num
	bytes := []byte(strconv.Itoa(num))
	for i := 0; i < len(bytes); i++ {
		for j := 0; j < len(bytes); j++ {
			bytes[i], bytes[j] = bytes[j], bytes[i]
			atoi, _ := strconv.Atoi(string(bytes))
			max = int(math.Max(float64(max), float64(atoi)))
			bytes[i], bytes[j] = bytes[j], bytes[i]
		}
	}
	return max
}

func trimMean(arr []int) float64 {
	sort.Slice(arr, func(i, j int) bool {
		return arr[i] < arr[j]
	})
	all := 0
	sum := 0
	s := len(arr) / 20
	e := len(arr) * 19 / 20
	for i := s; i < e; i++ {
		all += arr[i]
		sum++
	}
	return float64(all) / float64(sum)
}

func maxLengthBetweenEqualCharacters(s string) int {
	m := make(map[byte]int)
	a := []byte(s)
	ans := -1
	for i := range a {
		if v, ok := m[a[i]]; ok {
			ans = int(math.Max(float64(i-v-1), float64(ans)))
		} else {
			m[a[i]] = i
		}
	}
	return ans
}
